/**
 * 动态规划-不同路径II-力扣63
 */
public class Practice_8 {
    public static void main(String[] args) {
// int[][] obstacleGrid = {{0,0,0},{0,1,0},{0,0,0}};
        int[][] obstacleGrid = {{0,1},{0,0}};
        int result = uniquePathsWithObstacles(obstacleGrid);
        System.out.println(result);
    }
    public static int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m=obstacleGrid.length;
        int n=obstacleGrid[0].length;
        int[][] dp=new int[m][n];//dp为走到某个位置的方式有多少种。
        for(int i=0;i<m&&obstacleGrid[i][0]==0;i++){
            dp[i][0]=1;
        }
        for(int j=0;j<n&&obstacleGrid[0][j]==0;j++){
            dp[0][j]=1;
        }
        for(int i=1;i<m;i++){//注意从1开始，而不是从0开始，因为后续要减1
            for(int j=1;j<n;j++){//从1开始
                if(obstacleGrid[i][j]==0){
                    dp[i][j]=dp[i-1][j]+dp[i][j-1];
                }

            }
        }

        return dp[m-1][n-1];
    }
}
